﻿// 560. 和为 K 的子数组.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <vector>
#include <unordered_map>


using namespace std;
/*
https://leetcode.cn/problems/subarray-sum-equals-k/description/

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。
子数组是数组中元素的连续非空序列。


示例 1：
输入：nums = [1,1,1], k = 2
输出：2

示例 2：
输入：nums = [1,2,3], k = 3
输出：2


提示：
1 <= nums.length <= 2 * 104
-1000 <= nums[i] <= 1000
-107 <= k <= 107
*/


class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> mm;
        int presum[20010]; memset(presum, 0, sizeof presum);
        nums.insert(nums.begin(), 0);
        int ans = 0;
        for (int i = 1; i < nums.size(); i++) {
            presum[i] = presum[i - 1] + nums[i];
        }
        for (int i = 1; i < nums.size(); i++) {
            if (presum[i] == k) ans++;
            int find = presum[i] - k;
            ans += mm[find];
            mm[presum[i]]++;
        }

        return ans;
    }
};

int main()
{
    Solution s;
    vector<int> v{ 1,2,3 };
    s.subarraySum(v,3);
}
 